package org.newlucene.keywords;

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

import org.newlucene.core.analysis.Token;
import org.newlucene.core.analysis.UnicodeAnalyzer_NoStem;

class SuffixArray implements Comparable<SuffixArray>
{
	private String[] arr;
	
	public SuffixArray(String[] arr)
	{
		this.arr = arr;
	}
	
	public String[] getArray()
	{
		return arr;
	}
	
	public int length()
	{
		return arr.length;
	}
	
	public int compareTo(SuffixArray other)
	{
		// find out who has the shorter length first
		int len = this.arr.length <= other.length() ? this.arr.length : other.length();
		// compare the elements alphabetically
		for (int i = 0; i < len; i++)
		{
			int result = this.arr[i].compareTo(other.getArray()[i]);
			if (result > 0)
			{
				return 1;
			}
			else if (result < 0)
			{
				return -1;
			}
		}
		
		return this.arr.length > other.length() ? 1 : -1;
	}

	public String toString()
	{
		StringBuilder sb = new StringBuilder();
		for (String s : arr)
		{
			sb.append(s).append(" ");
		}
		sb.deleteCharAt(sb.length() - 1); // trim the last space
		
		return sb.toString();
	}
}

// for bootstrapping did you mean dictionary
public class PhraseGenerator 
{
	public static void main(String[] args) 
	{
		String text = "i love my mtv go dog go dog my mtv my mtv";
		
		List<String> strs = new ArrayList<String>();
		UnicodeAnalyzer_NoStem analyzer = new UnicodeAnalyzer_NoStem();
		analyzer.set(text);
		Token token;
		while ((token = analyzer.next()) != null)
		{
			strs.add(token.termText);
		}
		
		List<Phrase> phrases = getPhrases(strs, 2);		
		for (Phrase phrase : phrases)
		{
			System.out.println(phrase);
		}
	}

	public static List<Phrase> getPhrases(List<String> strs, int phraseLen)
	{
		// get suffix arrays
		SuffixArray[] sarrays = getSuffixArrays(strs);
		
		// sort the suffix arrays
		Arrays.sort(sarrays);
		
		// get over the suffix arrays and get the list of unique phrases
		List<Phrase> phrases = getUniquePhrases(sarrays, phraseLen);
		return phrases;
	}
		
	// assume the sarrays is already sorted
	private static List<Phrase> getUniquePhrases(SuffixArray[] sarrays, int phraseLen)
	{
		List<Phrase> phrases = new ArrayList<Phrase>();
		
		StringBuilder sb = new StringBuilder();

		String phraseText = null;
		int freq = 0;
		for (SuffixArray sarray : sarrays)
		{
			if (sarray.length() >= phraseLen)
			{
				// get the phraseText
				sb.delete(0, sb.length());
				for (int i = 0; i < phraseLen; i++)
				{
					sb.append(sarray.getArray()[i]).append(" ");
				}
				sb.deleteCharAt(sb.length() - 1);
				
				String newPhraseText = sb.toString();

				if (phraseText == null)
				{
					phraseText = newPhraseText;
//					freq++;
				}
				else
				{
					if (newPhraseText.equals(phraseText))
					{
						freq++;	// increment the count
					}
					else
					{
						phrases.add(new Phrase(phraseText, ++freq));	// we are done with a phrase
						// reset
						phraseText = newPhraseText;
						freq = 0;
					}
				}
			}
		}
		if (phraseText != null)
		{
			phrases.add(new Phrase(phraseText, ++freq));	// we are done with the last phrase
		}
		return phrases;
	}

	// return the list of suffix arrays
	private static SuffixArray[] getSuffixArrays(List<String> strs)
	{
		int strsLen = strs.size();
		
		SuffixArray[] suffixArrays = new SuffixArray[strsLen];
		
		// get the list of suffix arrays
		for (int i = 0; i < strsLen; i++)
		{
			// obtain a suffix array by going through the elements from i
			String[] sarray = new String[strsLen - i];
			int counter = 0;
			for (int j = i; j < strsLen; j++)
			{
				sarray[counter++] = strs.get(j);
			}
			suffixArrays[i] = new SuffixArray(sarray);
		}
		
		return suffixArrays;
	}
}